package 栈.柱状图中最大的矩形;

import java.util.Arrays;
import java.util.Stack;
/**
 * 题目描述：
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 力扣地址：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 * 力扣第84题
 * */
/**
 * 题目思路：
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * */

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 声明一个栈，用来保存柱子的索引
        Stack<Integer> s = new Stack<>();

        // 分别存储每个柱子左边和右边第一个小于它的柱子的位置
        int[] lefLower = new int[heights.length];
        int[] rigLower = new int[heights.length];

        // 初始化，默认左边界为-1，右边界为heights.length
        Arrays.fill(lefLower,-1);
        Arrays.fill(rigLower,heights.length);

        // 找每个柱子的右边界
        for(int i = 0; i < heights.length; i++) {
            while (!s.empty() && heights[s.peek()] > heights[i]) {
                rigLower[s.pop()] = i;
            }
            s.push(i);
        }

        // 清空栈，为找左边界做准备
        s = new Stack<>();

        // 找每个柱子的左边界
        for (int i = heights.length - 1; i >= 0; i--) {
            while(!s.empty() && heights[s.peek()] > heights[i]) {
                lefLower[s.pop()] = i;
            }
            s.push(i);
        }

        // 对于每一个柱子，求其能够扩展的最大矩形面积
        int res = 0;
        for(int i = 0; i < heights.length; i++) {
            res = Math.max(res, (rigLower[i] - lefLower[i] - 1) * heights[i]);
        }

        // 返回结果
        return res;
    }
}